package ljl.alg.jianzhioffer.round3.hard;

public class _19_isMatch {

    /**
     * 我自己写出来的，牛逼
     * 这个解法，比动态规划门槛低得多，也不是特别的慢
     */
    class fei_chang_good {
        public boolean isMatch(String s, String p) {
            return matches(s, 0, p, 0);
        }

        // a* aaaa
        // aa*a aaaa
        private boolean matches(String s, int i, String p, int j) {
            // i 结束了，j 只能是 * 结尾或也结束了
            if (i == s.length() && j == p.length()) return true;
            if (j == p.length()) return false;

            boolean equal = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
            // 如果带星，可以模式串不动匹配+，模式串+匹配串不动
            if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
                if (equal) {
                    return matches(s, i + 1, p, j) || matches(s, i, p, j + 2);
                } else
                    return matches(s, i, p, j + 2);
            } else if (equal) {
                return matches(s, i + 1, p, j + 1);
            }
            // 如果不带星，必须完全一样
            // 不一样则返回 false
            return false;
        }
    }

    class dp {
        public boolean isMatch(String s, String p) {
            int m = s.length() + 1, n = p.length() + 1;
            boolean[][] dp = new boolean[m][n];
            dp[0][0] = true;
            for(int j = 2; j < n; j += 2)
                dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
            for(int i = 1; i < m; i++) {
                for(int j = 1; j < n; j++) {
                    if(p.charAt(j - 1) == '*') {
                        if(dp[i][j - 2] ||
                                dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'))
                            dp[i][j] = true;
                    } else {
                        if(dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.'))
                            dp[i][j] = true;  // 1.
                    }
                }
            }
            return dp[m - 1][n - 1];
        }
    }

    class dp2 {
        public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();
            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0][0] = true;
            for (int i = 2; i <= n; i += 2) {
                if (p.charAt(i - 1) == '*')
                    dp[0][i] = true;
                else
                    break;
            }
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = p.charAt(j - 1) == '*' ?
                            dp[i][j - 2] ||
                                    dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'):
                            dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                }
            }
            return dp[m][n];
        }
    }
}
